package arithmetic.demo8;

import java.util.Arrays;

/**
 * 题目： dp_最长递增子序列
 */
class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        // 创建 dp
        int[] dp = new int[n];



        // 初始化
        Arrays.fill(dp,1);

        // 填表
        for(int i = 0 ; i < n; i++) {
            for(int  j = 0; j < i; j++) {
                if(nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        int ret = 0;
        for(int i = 0; i < n; i++) {
            ret = Math.max(ret, dp[i]);
        }

        return ret;
    }
}


/**
 * 题目： dp_子序列_摆动序列
 */

class Solution1 {
    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        // 创建 dp
        int[] gp = new int[n];
        int[] fp = new int[n];

        // 初始化
        Arrays.fill(gp,1);
        Arrays.fill(fp,1);


        int ret = 1;
        // 填表
        for(int i = 1; i < n;i++) {
            for(int j = 0; j < i; j++) {
                // 分情况填表
                if(nums[i] > nums[j]) {
                    // 如果是递增的情况
                    // 就在递减的状态下 + 1
                    // 寻找最大个数
                    gp[i] = Math.max(gp[i], fp[j] + 1);
                }else if(nums[i] < nums[j]) {
                    fp[i] = Math.max(fp[i], gp[j] + 1);
                }
            }

            // 更新最大个数结果
            ret = Math.max(ret, fp[i]);
            ret = Math.max(ret, gp[i]);
        }

        return ret;

    }
}




